/**
 * https://leetcode-cn.com/problems/sliding-window-maximum/
 * 滑动窗口的最大值
 * @param nums 
 * @param k 
 */
function maxSlidingWindow(nums: number[], k: number): number[] {
    // k为1, 原数组就是每个窗口的最大值
    if (k === 1) return nums

    // 获取长度
    let len = nums.length;

    // 最大窗口的值一共有 len - k + 1个
    // const ret = new Array(len - k + 1);
    const ret: number[] = [];

    // 队列
    const queue: number[] = [];

    
    // 先确定第一个窗口值的大小
    for (let i = 0; i < k; i++) {
        // 如果当前元素大于队列的队尾, 一直清空队尾直到>nums[m]
        while (queue.length && nums[i] >= nums[queue[queue.length - 1]]) {
            queue.pop();
        }
        // 将当前元素放入队列中
        queue.push(i);
    }
    // 当前元素第一个计入最大值中
    ret.push(nums[queue[0]])

    for (let i = k; i < len; i++) {
        // 如果当前元素大于队列的队尾, 一直清空队尾直到>nums[m]
        // 保证队头是最大的
        while (queue.length && nums[i] >= nums[queue[queue.length - 1]]) {
            queue.pop();
        }

        // 将当前元素放入队列中
        queue.push(i);

        // 队列的头无效, 清空队头
        while (i - k  >= queue[0]) queue.shift()

        // 计算窗口的最大值
        ret.push(nums[queue[0]])
    }
    return ret
};




function maxSlidingWindow4(nums: number[], k: number): number[] {
    // k为1, 原数组就是每个窗口的最大值
    if (k === 1) return nums

    // 获取长度
    let len = nums.length;

    // 最大窗口的值一共有 len - k + 1个
    // const ret = new Array(len - k + 1);
    const ret: number[] = [];

    // 队列
    const queue: number[] = [];

    // 不能计算窗口的最大值
    for (let i = 0; i < (k - 1); i++) {
        // 如果当前元素大于队列的队尾, 一直清空队尾直到>nums[m]
        while (queue.length && nums[i] > nums[queue[queue.length - 1]]) {
            queue.pop();
        }
        // 将当前元素放入队列中
        queue.push(i);
    }

    for (let i = k - 1; i < len; i++) {
        // 如果当前元素大于队列的队尾, 一直清空队尾直到>nums[m]
        while (queue.length && nums[i] > nums[queue[queue.length - 1]]) {
            queue.pop();
        }
        // 将当前元素放入队列中
        queue.push(i);

        // 计算窗口的最大值
        ret.push(nums[queue[0]])

        // 队列的头无效
        if (i - k + 1 >= queue[0]) queue.shift()

    }


    return ret;
};






const maxSlidingWindow3 = (nums: number[], k: number): number[] => {
    // k为1, 原数组就是每个窗口的最大值
    if (k === 1) return nums

    // 获取长度
    let len = nums.length;

    // 最大窗口的值一共有 len - k + 1个
    // const ret = new Array(len - k + 1);
    const ret: number[] = [];

    // 队列
    const queue: number[] = [Number.MIN_SAFE_INTEGER];

    // 移动的指针
    let l = - k + 1,
        m = 0


    while (m < len) {
        // 如果当前元素大于队列的队尾, 一直清空队尾直到>nums[m]
        while (nums[m] > nums[queue[queue.length - 1]]) {
            queue.pop();
        }
        // 将m加入队列中
        queue.push(m);

        if (l >= 0) {
            // 去窗口的最大值
            ret.push(nums[queue[0]])
        }


        m++;
        l++;
        if (l > queue[0]) {
            // 队头元素失效
            queue.shift() // 弹出队头
        }
    }


    return ret;
};




const maxSlidingWindow2 = (nums: number[], k: number): number[] => {
    const len = nums.length;
    // k 为1, 直接返回nums
    if (k === 1) return nums;


    /**
    * 求nums中s到e的最大值
    * @param s 
    * @param e 
    */
    const getMax = (s: number, e: number) => {
        let max = nums[s];
        for (let i = s + 1; i <= e; i++) {
            if (nums[i] > max) max = nums[i] // 大于max, 更新max
        }
        return max
    }


    const ret: number[] = new Array()



    // 只要滑动到len - k就行
    for (let i = 0; i <= len - k; i++) {
        ret.push(getMax(i, i + k - 1))
        break;
    }


    return ret
};

// console.log(maxSlidingWindow([1,3,-1,-3,5,3,6,7], 3))
// console.log(maxSlidingWindow([9, 10, 9, -7, -4, -8, 2, -6], 5))
// console.log(maxSlidingWindow([9,10,9,-7,-4,-8,2,-6], 5))